class Solution {
public:
 /*单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词，说明就是一个完全背包！  */
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        size_t size = s.size();
        vector<bool> dp(size+1, false);
        dp[0] = true;
        for(int i = 1; i <= size; ++i){
            for(int j = 0; j < i; ++j){
                string t = s.substr(j, i-j);
                if(dp[j] && dict.find(t) != dict.end()){
                    dp[i] = true;
                }
            }    
        }
        return dp[size];
    }
};